package com.leetcode.leetcode1;

/**
 *  删除链表的倒数第 N 个结点
 * @author: luhd
 * @create: 2021-08-31
 */
public class Practice19 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        //head = new ListNode(2,head);
        //head = new ListNode(3,head);
        //head = new ListNode(4,head);
        //head = new ListNode(5,head);
        ListNode listNode = removeNthFromEnd(head, 2);
        //System.out.println(listNode.val);
        //System.out.println(listNode.next.val);
        //System.out.println(listNode.next.next.val);
        //System.out.println(listNode.next.next.next.val);
    }
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个新链表，头节点为0，长度为head+1
        ListNode dummy = new ListNode(0,head);
        // 获取原链表的长度
        int length = getLength(head);
        // 将创建的新列表 赋给新列表
        ListNode cur = dummy;
        // 将 删除节点前面的向前移
        for (int i = 1; i < length-n+1; i++) {
            cur = cur.next;
        }
        // 将 删除节点的后面的内容  前移到 删除节点
        // 这边将 dummy中的节点删除(cur.next  会对dummy有影响)
        cur.next = cur.next.next;
        // 将dummy中的第一个空节点去掉  得到最后的结果
        ListNode ans = dummy.next;
        return ans;
    }
    public static int getLength(ListNode head){
        int length = 0;
        while(head!=null){
            length++;
            head = head.next;
        }
        return length;
    }
}
